public class test4 {
    //归并排序
    static int[] ret;

    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        mergrSort2(arr,0,arr.length-1);
        ret = new int[arr.length];
        for(int x:ret){
            System.out.print(x+" ");
        }
    }
    public  static void merge(int[] nums,int l,int r){
        if(l==r) return;
        int mid = (l+r)/2;
        merge(nums,l,mid);
        merge(nums,mid+1,r);
        int cur1 = l,cur2 = mid+1,i = 0;
        while (cur1<=mid && cur2<=r){
            if(nums[cur1]<nums[cur2]){
                ret[i++] = nums[cur1++];
            }
            else {
                ret[i++] = nums[cur2++];
            }
        }
        while (cur1<=mid){
            ret[i++] = nums[cur1++];
        }
        while (cur2<=r){
            ret[i++] = nums[cur2++];
        }
        for(i = l;i<=r;i++){
            nums[i] = ret[i-l];
        }

    }

    public static void mergrSort2(int[] nums ,int left,int right){
        //递归出口
        if(left==right){
            return;
        }
        //先排序两边
        int mid = (right+left)/2;
        mergrSort2(nums,left,mid);
        mergrSort2(nums,mid+1,right);
        //再合并两个有序数组
        int cur1 = left,cur2 = mid+1,i=0;
        while (cur1<=mid && cur2<=right){
            if(nums[cur1]<nums[cur2]){
                ret[i++] = nums[cur1++];
            }else{
                ret[i++] = nums[cur2++];
            }
        }
        //处理剩余未合并的数组
        while (cur1<=mid){
            ret[i++] = nums[cur1++];
        }
        while (cur2<=right){
            ret[i++] = nums[cur2++];
        }
        //重新赋值给nums数组
        for(int j = left;j<=right;j++){
            nums[j] = ret[j-left];
        }
    }
}
